{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分类\n",
    "分类简述：分类任务就是通过训练（或学习），得到一个目标函数或分类规则，把未知类别的数据对象（测试样本）划分到预定义的类别中。\n",
    "\n",
    "分类任务包含两个步骤：1）训练；2）测试（分类）\n",
    "\n",
    "训练：对于其属性和类别都已知的数据对象（即训练样本），通过寻找其中的规律，得到一个目标函数或分类规则的过程。\n",
    "\n",
    "测试（分类）：训练完成后，根据得到的目标函数或分类规则，将未知类别的数据对象（测试样本）划分到预定义的类别中。\n",
    "\n",
    "训练样本：训练过程中所使用的属性和类别都已知的数据对象即为训练样本。训练过程通过寻找其中的规律，得到一个目标函数或分类规则。\n",
    "\n",
    "测试样本：测试过程中所使用的，属性值已知但类别未知的数据对象即为测试样本。测试过程目标函数或分类规则，预测每个测试样本的类别。\n",
    "\n",
    "二、决策树分类的应用\n",
    "决策树工作原理：用决策树归纳分类\n",
    "\n",
    "什么是决策树？\n",
    "\n",
    "*类似于流程图的树结构\n",
    "\n",
    "*每个内部节点表示在一个属性上的测试\n",
    "\n",
    "*每个分枝代表一个测试输出\n",
    "\n",
    "*每个树叶节点代表类或类分布\n",
    "\n",
    "决策树的生成由两个阶段组成：\n",
    "\n",
    "*决策树构建\n",
    "\n",
    "开始时，所有的训练样本都在根节点； 递归的通过选定的属性，来划分样本 （必须是离散值）\n",
    "\n",
    "*树剪枝 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝 试图检测和剪去这种分枝\n",
    "\n",
    "决策树的使用：对未知样本进行分类 --> 通过将样本的属性值与决策树相比较\n",
    "\n",
    "2）如何建立决策树\n",
    "\n",
    "决策树构建 Hunt算法采用贪心策略构建决策树：在选择划分数据的属性时，采取一系列局部最优决策来构造决策树.\n",
    "\n",
    "决策树归纳的设计问题\n",
    "\n",
    "如何分裂训练记录 怎样为不同类型的属性指定测试条件? – (表示属性测试条件的方法) 怎样评估每种测试条件? – (选择最佳划分的度量) 如何停止分裂过程 当所有的记录属于同一类时，停止分裂 当所有的记录都有相同的属性时，停止分裂 提前终止树的生长\n",
    "\n",
    "3）ID3决策树\n",
    "\n",
    "怎样选择最佳划分？ ——不纯性的度量（1）→ 熵 选择最佳划分的度量通常是根据划分后子结点不纯性的程度。 不纯性的程度越低，类分布就越倾斜\n",
    "\n",
    "ID3算法——期望信息，熵 数据集D的期望信息又称熵 (entropy)，记作 Info(D)。 Info(D)又称为 D 的 熵 数据集D的熵描述了数据集D 的不纯性。 熵 ： I n f o ( D ) = − ∑ i = 1 m p i l o g 2 ( p i ) \\color{red}熵：Info(D)=-\\displaystyle\\sum_{i=1}^{m} p_ilog_2(p_i)熵：Info(D)=− i=1 ∑ m​p i​log 2​(p i​)\n",
    "\n",
    "Info(D)是识别D 中无组的类标号所需要的平均信息量。注意 ，此时我们所有的信息只是每个类的元组所占的百分比 。\n",
    "\n",
    "非负性： Info(D)大于等于0 连续性： Info(D)对任意q连续 极值性：当q都等于1/K时 ,Info(D)达到最大值\n",
    "\n",
    "熵的性质 数据集D的不纯度越高，期望信息，即熵的值越大 划分所依据的特征越有区分度，划分得到的数据子集D’（结 点）越纯，划分得到的数据子集D’的熵越小 即：划分所依据的特征越有区分度，划分得到的数据子集D’（结点）不纯度越小\n",
    "\n",
    "划分A的期望信息 度量一个划分的好坏–>期望信息 期 望 信 息 ： I n f o A ( D ) = − ∑ j = 1 v ∣ D j ∣ ∣ D ∣ I n f o ( D j ) \\color{red}期望信息：Info_A(D)=-\\displaystyle\\sum_{j=1}^{v} \\frac{|D_j|}{|D|}Info(D_j)期望信息：Info A​(D)=− j=1 ∑ v​\n",
    "\n",
    "∣D∣ ∣D j​∣​Info(D j​)\n",
    "\n",
    "ID3算法——信息增益 信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对 A 划分后1)之间的差。即 信 息 增 益 ： G r a i n ( A ) = I n f o ( D ) − I n f o A ( D ) \\color{red}信息增益：Grain(A)=Info(D)-Info_A(D)信息增益：Grain(A)=Info(D)−Info A​(D) 换言之 ，Gain(A) 告诉我们通过 A 上的划分我们得到了多少 。它是知道 A 的值而导致的信息需求的期望减少。 选择具有最高信息增益 Gain (A) 的属性 A 作为结点 N 的分裂属性。 这等价于在“能做最佳分类”的属性 A上划分，使得完成元组分类还需要的信息最小(即最小化 Gain (A) )\n",
    "\n",
    "一个标记类的元组的训练集 D ，随机地从AlIElectronics顾客数据库中选取。 在这个例子中，每个属性都是离散值的，连续值属性已经被离散化。 类标号属性buys_compter有两个不同值(即{yes,no})，因此有两个不同的类(即m=2)。设类C1对应于yes，而类C2对应于no。 类yes有9个元组，类no有5个元组。为D中的元组创建(根)。结点N。为了找出这些元组的分裂准则，必须计算每个属性的信息增益。 下一步，需要计算每个属性的期望信息需求。从属性age开始。需要对age 的每个类考察 yes 和 no 元组的分布。\n",
    "\n",
    "由于age在属性中具有最高的信息增益，所以它被选作分裂属性。结点N用age标记，并且每个属性值生长出一个分枝。然后元组据此划分，如图所示。\n",
    "\n",
    "4）表示属性测试条件的方法 怎样为不同类型的属性指定测试条件?\n",
    "\n",
    "依赖于属性的类型：①标称 ②序数 ③连续 依赖于划分的路数：①2路划分 ②多路划分 基于标称属性的划分 多路划分: 划分数（输出数）取决于该属性不同属性值的个数. 二元划分: 划分数为2，这种划分要考虑创建k个属性值的二元划分的所有2 k − 1 − 1 2^{k-1}-12 k−1 −1种方法.\n",
    "\n",
    "基于序数属性的划分 多路划分: 划分数（输出数）取决于该属性不同属性值的个数. 二元划分: 划分数为2，需要保持序数属性值的有序性\n",
    "\n",
    "基于连续属性的划分 多路划分: v i v_iv i​≤ \\leq≤A ＜ v i + 1 （ i = 1 , … , k ) A＜vi+1（i=1,…,k)A＜vi+1（i=1,…,k) 二元划分: ( A < v ) (A < v)(A<v) or ( A ≥ v ) (A ≥v)(A≥v) –考虑所有的划分点，选择一个最佳划分点v\n",
    "\n",
    "5）选择最佳划分的度量 选择最佳划分的度量通常是根据划分后子结点不纯性的程度。不纯性的程度越低，类分布就越倾斜\n",
    "\n",
    "怎样选择最佳划分？ ——不纯性的度量（2）→ Gini（基尼指数）、classification error\n",
    "\n",
    "不纯性的测量: GINI 给定结点t的Gini值计算 : G I N I ( t ) = 1 − ∑ j [ p ( j ∣ t ) ] 2 \\color{red}GINI(t)=1-\\displaystyle\\sum_{j}[p(j|t)]^2GINI(t)=1− j ∑​[p(j∣t)] 2\n",
    "\n",
    "( p ( j ∣ t ) p( j | t)p(j∣t) 是在结点t中，类j发生的概率 ).\n",
    "\n",
    "当类分布均衡时，Gini值达到最大值 相反当只有一个类时，Gini值达到最小值0 GINI值越小，纯度越大\n",
    "\n",
    "不纯性的测量: Classification Error 给定结点t的 Classification Error值计算 : E r r o r ( t ) = 1 − max ⁡ j P ( i ∣ t ) \\color{red}Error(t)=1-\\displaystyle\\max_{j}P(i|t)Error(t)=1− j max​P(i∣t)\n",
    "\n",
    "当类分布均衡时， error值达到最大值 (1 − 1 / n c 1 - 1/n_c1−1/n c​) 相反当只有一个类时， error值达到最小值0 ERROR值越小，纯度"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
